package com.leetcode.No0032;

import org.junit.Test;

/**
 * @program: leetcode
 * @description: 最长有效括号 贪心算法（正反双向）
 * @author: wangzhihua
 * @date: 2021-06-27
 */
public class Solution03 {
	@Test
	public void test01() {
		System.out.println(longestValidParentheses(""));
		System.out.println(longestValidParentheses("(()"));
		System.out.println(longestValidParentheses(")()())"));
		System.out.println(longestValidParentheses("()()()"));
		System.out.println(longestValidParentheses("(()()(())(("));
		System.out.println(longestValidParentheses("))))())()()(()"));
	}

	public int longestValidParentheses(String s) {
		int len = s.length();
		if (len == 0) {
			return 0;
		}

		char[] brackets = s.toCharArray();
		int ans = 0;

		int left = 0;
		int right = 0;
		for (int i = 0; i < len; ++i) {
			if (brackets[i] == '(') {
				++left;
			} else {
				++right;
			}
			if (left == right) {
				ans = Math.max(ans, left << 1);
			} else if (left < right) {
				left = 0;
				right = 0;
			}
		}

		left = 0;
		right = 0;
		for (int i = len - 1; i >= 0; --i) {
			if (brackets[i] == '(') {
				++left;
			} else {
				++right;
			}
			if (left == right) {
				ans = Math.max(ans, left << 1);
			} else if (left > right) {
				left = 0;
				right = 0;
			}
		}

		return ans;
	}

}
